In a collection of computing devices, a data item may be multiply replicated to create a number of copies of the item on the different computing devices and/or possibly within a single device. An item may be any stored data object, such as for example contact or calendar information, stored pictures or music files, software application programs, files or routines, etc. The collection of computing devices may for example be a desktop computer, a remote storage server, a personal digital assistant (PDA), a cellular telephone, etc. The group of all such items and replicas where the items are stored may be referred to as a distributed collection.
In many cases, a user would like all of their various data storing devices to have the latest updated information without having to manually input the same changes into each device data store. Replication, or synchronization, of data is one process used to ensure that each data store has the same information. Synchronization protocols are the means by which devices exchange created and updated versions of items in order to bring themselves into a mutually consistent state. The periodicity of the sync may vary greatly. Networked devices may sync with each other frequently, such as once every minute, hour, day, etc. Alternatively, devices may sync infrequently, such as for example where a portable computing device is remote and disconnected from a network for a longer period of time. Whether the synchronization is frequent or infrequent, the distributed collection is said to be weakly-coherent if, in any given instant, devices may have differing views of the collection of items because items updated at one device may not yet be known to other devices.
As an example, a user may maintain an electronic address book or a set of email messages in a variety of different devices or locations. The user may maintain the address book or email addresses, for example, on a desktop computer, on a laptop computer, on a PDA and/or on a mobile phone. The user may modify the contact information or send/receive email addresses using applications associated with each location. Regardless of where or how a change is made, one goal of replication is to ensure that a change made on a particular device or in a particular location is ultimately reflected in the data stores of the other devices and in the other locations.
FIG. 1 illustrates a weakly-coherent distributed collection, including multiple replicas 20 (one of which is labeled), designated A through F. Each replica A through F may be a computing device including a data store and associated processor. However, as is known, a single computing device may include several replicas, and a single replica may be implemented using more than one computing device. In the example of FIG. 1, the replicas may include a desktop computer A, a pair of laptop computers B and C, a cellular telephone D, a personal digital assistant (PDA) E and a digital camera F. The number and type of replicas is by way of example and may be more, less and/or different than shown. FIG. 1 further shows communication links 22 (one of which is labeled) between the various replicas to establish a peer-to-peer network.
Synchronization between replicas may be described as a sharing of knowledge between replicas. In particular, each replica 20 may create a new version of an item, either when it creates the first version of a new item, or when it updates an existing version of an item to create a new version of the item. A common knowledge sharing scheme involves tracking, within each replica, changes that have occurred to one or more items subsequent to a previous replication. One such tracking scheme makes use of version vectors, which consist of lists of version numbers, one per replica, where each version number is an increasing count of updates made to an item by a replica. During synchronization, one replica sends version vectors for all of its stored items to another replica, which uses these received version vectors to determine which updated items it is missing. Comparing the version vectors of two copies of an item tells whether one copy is more up-to-date (every version number in the up-to-date copy is greater than or equal to the corresponding version number in the other copy) or whether the two copies conflict (the version vectors are incomparable). The replica may then update its copy of the item if required or make efforts to resolve the detected conflict. Other knowledge sharing schemes are known. By repeating the synchronization process between replicas, all replicas eventually learn about the most up-to-date versions of each item.
Group policy is well known for coherent networks for setting desired configurations and access permissions at a single domain controller. These configurations and permissions may then be systematically applied to one or more groups of users and/or computers across a network. Group policy employs a collection of settings, referred to as group policy objects (“GPO”), that define what one or more computing devices will look like and how they will behave for one or more defined group of users. In addition to allowing disparate privileges to different user groups, group policy also allows software installations, updates and changes to be applied across an entire network of computers via a simple change to an existing GPO. This reduces the administrative burden and costs associated with managing these resources.
Group policy works in coherent networks in part because the creation and management of policy is logically centralized, for example in a central controller. When a new policy is created or updated, it is sent out to all nodes in the network simultaneously. When a computing device of the coherent network receives a new or updated policy, authenticated to be from the central controller, there is no question of its validity or whether it might be in conflict with another policy received from another source.
The same cannot be said of a weakly-coherent distributed collection. Such collections are by definition formed of autonomous, decentralized devices, in which replicas sync to each other sporadically and updates may occur in parallel. This can lead to conflicts which can have significant consequences when dealing with policy and security in a weakly replicated system.
For example, in prior art FIG. 1, laptops B and C, disconnected from each other, may update access control policy for an item or set of items without knowledge of the other's change. When another replica receives the changes, it may not be possible to resolve which policy to implement. As another example, replica A may update access control policy to remove rights of replica B to perform policy updates. Replica B could learn of this, but ignore it and instead create a policy update revoking replica A's right to perform policy updates. A replica rejoining the system may have no way of resolving the conflict. As a still further example, an access control policy may exist for the collection, possibly indicating that an item may not be updated. Under the framework with which conventional weakly-replicated systems operate, a replica may rewrite that policy and then update that item.
There is, therefore, a need of a framework for implementing an access control policy addressing the problems inherent in a weakly-coherent distributed collection.